import java.util.*;
class TreeNode {
    int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
        TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
     }
  }

public class Test {
    // 题目1：叶子相似的树
    // 思路：使用两个队列去存储每颗树的叶子节点
    public boolean leafSimilar1(TreeNode root1, TreeNode root2) {
        Deque<TreeNode> que1 = new LinkedList<>();
        Deque<TreeNode> que2 = new LinkedList<>();
        queue(que1,root1);
        queue(que2,root2);

        if(que1.size() != que2.size()){
            return false;
        }

        while(!que1.isEmpty()){
            if(que1.poll().val != que2.poll().val ){
                return false;
            }
        }

        return true;
    }

    private TreeNode queue(Deque<TreeNode> que, TreeNode root){
        if(root == null){
            return root;
        }

        TreeNode left = queue(que, root.left);
        TreeNode right = queue(que, root.right);

        if(right == null && left == null){
            que.offer(root);
        }
        return root;
    }

    // 写法二：
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();

        dsf(list1, root1);
        dsf(list2, root2);

        return list1.equals(list2);
    }

    private void dsf(List<Integer> list, TreeNode root){
        if(root == null){
            return ;
        }

        if(root.left == null && root.right == null){
            list.add(root.val);
        }

        dsf(list, root.left);
        dsf(list, root.right);
    }

    // 题目2 ：二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        TreeNode cur = root;
        TreeNode rightMost = null;
        while(cur != null){
            rightMost = cur.left;
            if(rightMost != null){
                while(rightMost.right != null && rightMost.right != cur){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    list.add(cur.val);
                    rightMost.right = cur;
                    cur = cur.left;
                }else{
                    rightMost.right = null;
                    cur = cur.right;
                }
            }else{
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }

    // 题目3：二叉树的直径
    // 1. 递归，返回的是以该节点根节点，最大的深度
    // 2.  left + right ，得到以该节点作为根节点的最大直径
    // 3. 所以 max 取 left + right 与 max 的最大值，得到的就是整个二叉树中，任意两个节点的最大直径
    int max;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;

    }

    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = depth(root.left);
        int right =depth(root.right);

        max = Math.max(left + right, max);

        return Math.max(left, right) + 1;
    }

    // 题目4：二叉搜索树的最小绝对差
    // 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
    //
    //差值是一个正数，其数值等于两值之差的绝对值。
    // 中序遍历 again~~
    int pre = -1;
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dsf(root);
        return min;
    }

    private void dsf(TreeNode root){
        if(root == null){
            return;
        }

        dsf(root.left);
        if(pre != -1){
            min = Math.min(min, root.val - pre);
        }
        pre = root.val;
        dsf(root.right);
    }

    // 题目5：二叉树的坡度
    // 给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。
    //
    //一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
    //
    //整个树 的坡度就是其所有节点的坡度之和。
    int sum;
    public int findTilt(TreeNode root) {
        sumSubTree(root);
        return sum;
    }

    private int sumSubTree(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = sumSubTree(root.left);
        int right = sumSubTree(root.right);

        sum += Math.abs(left - right);
        return left + right + root.val;
    }

    // 题目6：二叉树中第二小的节点
    // 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
    //
    //更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。
    //
    //给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。
    //
    //如果第二小的值不存在的话，输出 -1 。
    public static void main1(String[] args) {
        System.out.println(Integer.MAX_VALUE);
    }

    long min1 = Long.MAX_VALUE;
    public int findSecondMinimumValue(TreeNode root) {
        dsf1(root);
        return (int)(min1 == Long.MAX_VALUE ? -1 : min1);
    }

    private void dsf1(TreeNode root){
        if(root == null){
            return ;
        }

        if(root.left == null && root.right == null){
            return ;
        }

        if(root.val == root.left.val && root.val == root.right.val){
            dsf1(root.left);
            dsf1(root.right);
            return;
        }

        if(root.val == root.left.val){
            dsf1(root.left);
            min1 = Math.min(min,root.right.val );
            return;
        }

        if(root.val == root.right.val){
            dsf1(root.right);
            min1 = Math.min(min,root.left.val );
            return;
        }
    }

    // 官方题解：
    // 更简练
    int ans;
    int rootVal;
    public int findSecondMinimumValue1(TreeNode root) {
        ans = -1;
        rootVal = root.val;
        dsf2(root);
        return ans;
    }

    private void dsf2(TreeNode root){
        if(root == null){
            return ;
        }

        if(ans != -1 && root.val >= ans){
            return;
        }

        if(root.val > rootVal){
            ans = root.val;
        }

        dsf2(root.left);
        dsf2(root.right);
    }

}
